package com.leet.tree;

public class DeleteNode {
    public int rightMin(TreeNode root){
        root = root.right;
        while(root.left != null){
            root = root.left;
        }
        return root.val;
    }
    public int leftMax(TreeNode root){
        root = root.left;
        while(root.right != null){
            root = root.right;
        }
        return root.val;
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(root.val < key){
            root.right = deleteNode(root.right, key);
        }else if(root.val > key){
            root.left = deleteNode(root.left, key);
        }else{
            if(root.left == null && root.right == null) root = null;
            else if(root.left != null) {
                root.val = leftMax(root);
                root.left = deleteNode(root.left, root.val);
            }
            else {
                root.val = rightMin(root);
                root.right = deleteNode(root.right, root.val);
            }
        }
        return root;
    }
}
